package impl;

import anaydis.sort.SorterType;
import org.jetbrains.annotations.NotNull;

import java.util.Comparator;
import java.util.List;

public class QuickSorter extends AbstractSorter{

    public QuickSorter(){
        super(SorterType.QUICK);
    }

    public <T> void sort(Comparator<T> tComparator, List<T> ts){
        int i = partition(tComparator, ts, 0 , ts.size(), ts.size()-1);
        sort(tComparator, ts, 0 , i);
        sort(tComparator, ts, i , ts.size());
    }

    public <T> void sort(Comparator<T> tComparator, List<T> ts, int desde, int hasta){
        int i;
        if(hasta>1){
            i = partition(tComparator, ts, desde , hasta, hasta-1);
        }else{
            i=2;
        }
        if(i - desde > 1 && i>2){
            sort(tComparator, ts, desde , i);
        }else{
            if(greater(tComparator, ts, 0, 1)){
                swap(ts, 0, 1);
            }
        }

        if(hasta - i > 1 && hasta>3){
            sort(tComparator, ts, i , hasta);
        }
/*
        //chequeos
        boolean bienOrdenado = true;
        for(int g = 0; g<ts.size()-1;g++){
            if(greater(tComparator, ts, g, g+1)){
                bienOrdenado = false;
            }
        }
        System.out.println(bienOrdenado);
*/
    }

    /*partition ubica el pivote en su posicion final, y a todos los mayores
    *a el a la derecha y los menores o iguales a izquierda.
    *Return indice final del pivote
    */

    private <T> int partition(Comparator<T> tComparator, List<T> ts,int desde, int hasta, int pivote){
        int i = desde;
        int j = hasta-2;
            boolean end = false;
            do{
                boolean imayor = false;
                do{                         //busca el primer elemento mayor al pivote
                    if(greater(tComparator, ts, i,pivote)){
                        imayor = true;
                    }else{
                        i++;
                    }
                }while((!imayor) && i<j+1);     // si i>=j+1, entonces los indices se cruzaron y "i" es la posicion final del pivote
                    boolean jmenor = false;
                    do{                         //busca el ultimo elemento menor al pivote
                        if(!(greater(tComparator, ts, j,pivote))){
                            jmenor = true;
                        }else{
                            j--;
                        }
                    }while((!jmenor) && i<j+1);
                    if(i<j){                    //si los indices no se cruzaron todavia, intercambia los elementos
                        swap(ts, i, j);
                    }
                    else{                       //si ya se cruzaron, ubica el pivote en su nueva posicion
                        if(i<pivote){
                            swap(ts,i,pivote);
                        }
                        end = true;
                    }
            }while(end == false);
/*
            //chequeos
            System.out.println("Valor del pivote: "+ts.get(i));
            System.out.println("Posicion final pivote: "+i);
            System.out.print("OrdenParcial: ");
            for(int asd = 0; asd<ts.size(); asd++){
                System.out.print(" "+ts.get(asd));
        }
        System.out.println();
*/
        return i;
    }

    @NotNull
    public SorterType getType(){
        return SorterType.QUICK;
    }
}
